The present invention relates to the hierarchical structures, and in particular to systems and methods for constructing bounding volume hierarchical structures.
Hierarchical structures, such as logical tree structures, are known in many technical fields, and are employed to organize information in a logical form to facilitate storage and retrieval of the information. In a typical implementation, the highest node or “root” of the logical tree includes the most general information, with descendant nodes (i.e., child nodes, grandchild nodes, etc. moving away from the root node) providing additional detail as to a particular aspect of the information represented by the tree structure. It is, or course, desirable to navigate through the tree via the shortest path and/or in the shortest amount of time in order to store or retrieve information, and techniques for constructing a hierarchical structure which minimizes the time to traverse the tree occupies engineers and scientists from a variety of different fields.
In the areas of graphics processing and rendering, ray tracing is a field which uses hierarchical structures for organizing information. Ray tracing involves a technique for determining the visibility of an object (e.g., a geometric primitive) from a given point in space, for example, an eye, or camera perspective. Primitives of a particular scene which are to be rendered are typically located in nodes, and the nodes organized within a hierarchical tree. Ray tracing involves a first operation of “node traversal,” whereby nodes of the tree are traversed in a particular manner in an attempt to locate nodes having primitives, and a second operation of “primitive intersection,” in which a ray is intersected with one or more primitives within a located node to produce a particular visual effect.
Preliminary to node traversal and primitive intersection testing, the hierarchical structure is built to efficiently organize the objects, the hierarchical structure constructed by partitioning a higher level node (e.g., a parent node) into two or more lower level nodes (e.g., child nodes), each child node defining a successively smaller space or including successively fewer objects compared to the parent node. The partitioning process is repeated for each of the child nodes, whereby each child is further partitioned into two grandchild nodes, each grandchild node defining a successively smaller space or including successively fewer objects as the child node from which it originates. The process repeats until the last generate of nodes include a single object.
Conventionally, the construction of hierarchical structures employs one of two different types of partitioning techniques: spatial partitioning or object partitioning. Spatial partitioning involves recursively subdividing a given space and distributing the geometric primitives into the resulting partitions. Each primitive is inserted into all partitions it overlaps, potentially resulting in multiple references for a primitive. This process is repeated until some termination criterion is met. K-dimensional trees (kD-trees) represents one type of hierarchical structure which employs this spatial partitioning technique. In particular, kD-trees implement binary spatial partitioning using one axis aligned plane per node. An advantageous property of kD-trees is their ability to adapt to arbitrary scenes with highly varying geometric densities, thereby providing excellent culling efficiency even in difficult settings. A disadvantage of kD-trees is that they suffer from high memory consumption due to deep trees and high primitive/reference duplication.
Object partitioning represents a second technique, whereby objects are recursively divided into disjoint sets. The sets are stored in bounding volumes represented as nodes of the hierarchical tree, with the bounding volumes having arbitrary overlap with each other. Such overlapping regions are expensive during traversal, because rays that intersect these regions must traverse each node which contributes to the overlap, i.e., a ray must visit each node to test for an intersection with an object therein. Advantageously, bounding volumes can be handled very efficiently and in most cases enclose primitives reasonably well. Since in a conventional BVH each primitive is referenced exactly once, the hierarchies consist of fewer nodes than kD-trees for virtually all scenes.
As can be understood from the foregoing, each of the spatial and object partitioning techniques used in constructing hierarchical structures has benefits, and what is needed is to develop a system and corresponding method for constructing a hierarchical structure which combines the advantages of both.